package org.jkuang.qstar.commons.util;

import java.util.concurrent.atomic.AtomicInteger;
/**
 * 
 * @author jkuang 2012年11月17日
 *
 */
public class BTreeIndex {
	private BTreeBlock[] blocks;
	private AtomicInteger blockssize = new AtomicInteger();
	private AtomicInteger nodessize = new AtomicInteger();
	private final int MAX_NODES_SIZE = 0x8fff;
	private final int CAPACITY;

	public BTreeIndex(int capacity) {
		this.CAPACITY = capacity;
		this.blocks = new BTreeBlock[CAPACITY];
	}

	/**
	 * 查找node节点属于哪个数据块
	 * 
	 * @param node
	 * @param type
	 * @return
	 */
	int indexOfBlcok(long node, SerarChType type) {
		int fromIndex = 0;
		int toIndex = this.blocks.length - 1;
		while (fromIndex <= toIndex) {
			int mid = (fromIndex + toIndex) >> 1;
			int cmp = blocks[mid].rangeContains(node);
			if (cmp < 0)
				fromIndex = mid + 1;
			else if (cmp > 0)
				toIndex = mid - 1;
			else
				return mid; // key found
		}
		switch (type) {
		case _floor:
			return toIndex;
		case _ceil:
			return fromIndex;
		default:
			if (fromIndex > this.blocks.length - 1) {
				return this.blocks.length - 1;
			} else {
				return fromIndex;
			}
		}
	}

	boolean combineBlock(int index) {
		if (blocks[index].size() == 0) {
			int numMoved = this.blockssize.get() - index - 1;
			if (numMoved > 0) {
				BTreeBlock[] newBlocks = new BTreeBlock[this.blockssize.get() - 1];
				System.arraycopy(blocks, 0, newBlocks, 0, index);
				System.arraycopy(blocks, index + 1, newBlocks, index, numMoved);
				this.blocks = newBlocks;
				this.blockssize.decrementAndGet();
			} else {
				BTreeBlock[] newBlocks = new BTreeBlock[this.blockssize.get()];
				System.arraycopy(blocks, 0, newBlocks, 0, index);
				this.blocks = newBlocks;
				this.blockssize.decrementAndGet();
			}
		}
		return false;
	}

	void splitBlock(int index) {
		if (blocks[index].size() > MAX_NODES_SIZE) {
			BTreeBlock[] temps = blocks[index].splitToTwo();
			BTreeBlock[] newBlocks = new BTreeBlock[this.blockssize.incrementAndGet()];
			System.arraycopy(blocks, 0, newBlocks, 0, index);
			System.arraycopy(blocks, index, newBlocks, index + 1, this.blockssize.get() - 1 - index);
			newBlocks[index] = temps[0];
			newBlocks[index + 1] = temps[1];
			this.blocks = newBlocks;
		}
	}

	/**
	 * 插入数据
	 * 
	 * @param node
	 */
	public void insert(long key, int doc) {
		if (this.blockssize.get() == 0) {
			this.blocks[this.blockssize.getAndIncrement()] = new BTreeBlock();
			this.blocks[this.blockssize.get() - 1].insert(key, doc);
			this.nodessize.incrementAndGet();
		} else if (this.blocks[this.blockssize.get() - 1].rangeContains(key) <= 0) {
			if (this.blocks[this.blockssize.get() - 1].insert(key, doc) >= 0) {
				splitBlock((int) (this.blockssize.get() - 1));
				this.nodessize.incrementAndGet();
			}
		} else {
			int index = indexOfBlcok(key, SerarChType._index);
			if (this.blocks[index].insert(key, doc) >= 0) {
				splitBlock(index);
				this.nodessize.incrementAndGet();
			}
		}
	}

	/**
	 * 删除数据
	 * 
	 * @param node
	 * @return
	 */
	public boolean remove(long key) {
		if (blockssize.get() == 0) {
			return false;
		} else if (this.blocks[blockssize.get() - 1].rangeContains(key) == 0) {
			boolean result = this.blocks[blockssize.get() - 1].delete(key) >= 0;
			if (result) {
				combineBlock((int) (blockssize.get() - 1));
				this.nodessize.decrementAndGet();
			}
			return result;
		} else {
			int index = indexOfBlcok(key, SerarChType._index);
			boolean result = this.blocks[index].delete(key) >= 0;
			if (result) {
				combineBlock(index);
				this.nodessize.decrementAndGet();
			}
			return result;
		}
	}

	public int get(long key) {
		int low = 0;
		int high = blockssize.get() - 1;
		while (low <= high) {
			int mid = (low + high) >> 1;
			int cmp = this.blocks[mid].rangeContains(key);
			if (cmp < 0)
				low = mid + 1;
			else if (cmp > 0)
				high = mid - 1;
			else {
				return this.blocks[mid].get(key);// (node);
			}
		}
		// key not found
		return -1;
	}

}
